
from Code_Link_02 import ListNode
from Code_Link_02 import printLink
from Code_Link_02 import printCycLink

''' 
https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
https://leetcode.cn/problems/linked-list-cycle-ii/
环形链表
判断是否有环，slow fast快慢指针，slow走1，fast走2,最终会相遇
fast - slow = 环的节点数 fast比slow多跑一圈
a ... b ...c 
      ......
b是环入口，c是slow fast相遇点，求a 到 b的节点数
设 a...b距离是x, b...c的距离是y, c...b的距离是z
x + y = slow (slow指针走的节点数）
x + y + z + y = fast (fast比slow x+y 多走了一圈z+y)
2*(x+y) = x+y +z +y (fast是slow的2倍，因为slow走1步，fast走2步)
综上 x = z 那么从c走到b，等同于a走到b
c的指针slow a的指针head,同时走，当走到b时相遇，即得出b节点（重点！！！！！）
'''
def l142(head:ListNode):
    slow = fast = head
    while slow and fast.next:
        slow = slow.next
        if fast.next.next == None:break
        fast = fast.next.next

        if slow == fast: #当快慢指针相遇
            index2 = head #x节点数的头节点
            index1 = slow #z节点数的头节点
            while index2:
                if index1 == index2:#相遇
                    return index1 #返回相遇的节点，环入口节点
                index1 = index1.next
                index2 = index2.next
    return None #不满足上面条件的是无环

if __name__ == '__main__':
    head = ListNode(3)
    cur = head
    # pos = cur  # 开始环的点 pos 3
    cur.next = ListNode(2)
    cur = cur.next
    cur.next = ListNode(1)
    cur = cur.next
    cur.next = ListNode(-4, next=None)
    res = l142(head)
    print(res.val)

    #3 -> 2 -> 1 -> -4 pos = 1 从2开始环
    # head = ListNode(3)
    # cur = head
    # cur.next = ListNode(2)
    # cur = cur.next
    # r = l142(cur)
    # printLink(r)
    # pos = cur #开始环的点
    # cur.next = ListNode(1)
    # cur = cur.next
    # cur.next = ListNode(-4)
    # cur = cur.next
    # cur.next = pos
    # res = l142(head)
    #
    # printCycLink(pos)
    # printCycLink(res)
    #l206(link6)
    pass